package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

import java.util.PriorityQueue;

public class leetcode20241007 {
    public int minRefuelStops(int target,int startFuel,int[][] stations){
        if(stations.length==0){
            return startFuel>=target ? 0 : -1;
        }
        int sum=startFuel,ans=0;
        // 大根堆
        PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)->{
            return o2-o1;
        });
        for(int i=0;i<stations.length;i++){
            while(sum<stations[i][0]){
                Integer fuel=pq.poll();
                if(fuel==null){
                    return -1;
                }
                sum+=fuel;
                ans++;
            }
            pq.add(stations[i][1]);
        }

        while(sum<target){
            Integer fuel=pq.poll();
            if(fuel==null){
                return -1;
            }
            sum+=fuel;
            ans++;
        }
        return ans;
    }
}
